package gss.generator;

import java.util.*;
import java.io.*;

import java.util.List;
import java.util.ArrayList;

import java.util.Random;

import org.apache.commons.math.fraction.BigFraction;

import gss.LineSegment;
import gss.Vertex;

import external.RandomIterator;

public class Generator {
	private static ArrayList<LineSegment> linesegs = new ArrayList<LineSegment>();
	/** A set of vertices with distinct coordinates */
	private static ArrayList<Vertex> intersections = new ArrayList<Vertex>();

	private static Random rdm = new Random();

	//determines location to print text file
	private static String gssfile;
	private static String matrixfile;

	//segnum is the number of line segments
	private static int segnum = 20;
	private static int gridsize = segnum;

	//assign probabilities to various line segment generation methods
	private static double probRandomSeg = .6;
	private static double probVertexToVertex = .2;
	//private static double probVertexToRandom = .2;

	/**
	 * @param args
	 */	
	public static void main(String[] args) throws java.io.IOException {
		// parse command line arguments
		// segnum gridsize probRandomSeg probVertexToVertex probVertexToVertex gssfile matrixfile
		if (args.length < 6) {
		    System.err.println("Incorrect number of arguments.");
		    System.err.println("Arguments: segnum gridsize probRandomSeg probVertexToVertex probVertexToVertex gssfile matrixfile");
		    System.exit(1);
		} else {
		    segnum = Integer.parseInt(args[0]);
		    gridsize = Integer.parseInt(args[1]);
		    probRandomSeg = Double.parseDouble(args[2]);
		    probVertexToVertex = Double.parseDouble(args[3]);
		    if (probRandomSeg + probVertexToVertex > 1) {
			System.err.println("probabilities must add to <= 1");
			System.exit(1);
		    }
		    gssfile = args[4];
		    matrixfile = args[5];
		}
			
		//create first line segment
		addSegment(randomSegment(), linesegs, intersections);

		//creates 3 more line segs, to allow VertToVert
		for(int j = 1; j<=3; j++){
			addSegment(randomIntersectingSegment(linesegs, j), linesegs, intersections);
			// delete me !!! this is for testing only!!
			for(LineSegment seg : linesegs){
				System.out.println(seg.toString());
			}
		}

		//continue until fully populated
		for(int i = 4;linesegs.size()<segnum; i++){
			double createType = Math.random();


			//creates a random segment if chosen
			if(createType <= probRandomSeg){
				addSegment(randomIntersectingSegment(linesegs, i), linesegs, intersections);
			}

			//connects a vertex to a vertex if chosen
			else if(createType < probRandomSeg + probVertexToVertex){
				LineSegment seg = vertexToVertex(intersections, linesegs, i);
				// vertexToVertex has a possibility of failing, hence this test
				if (seg == null) { seg = randomIntersectingSegment(linesegs, i); }
				addSegment(seg, linesegs, intersections);
			}

			//creates a random segment with a vertex as a firstpt if chosen
			else{
				addSegment(vertexToRandom(intersections, linesegs, i), linesegs, intersections);
			}

			// delete me !!! this is for testing only!!
			for(LineSegment seg : linesegs){
				System.out.println(seg.toString());
			}
		}

		// print the line segments to a text file
		BufferedWriter gssout = null;
		BufferedWriter matrixout = null;
		try{
			// write gss file
			gssout = new BufferedWriter(new FileWriter(gssfile));
			ArrayList<String> seg_names = new ArrayList<String>(linesegs.size());
			for(LineSegment templine : linesegs){
				seg_names.add(templine.getName());
				gssout.write(templine.getX1()+" "+
						templine.getY1()+" "+ templine.getX2()+" "+templine.getY2());
				gssout.newLine();
			}

			//  write adjacency matrix
			matrixout = new BufferedWriter(new FileWriter(matrixfile));
			for(Vertex v : intersections) {
				matrixout.write(v.toAdjacencyMatrixRow(seg_names));
				matrixout.newLine();
			}
		}
		catch (Exception e){
			System.err.println("Error: " + e.getMessage());
		} finally {
			if (gssout != null) { gssout.close(); }
			if (matrixout != null) { matrixout.close(); }
		}
	}//end main
	
	/**
	 * Adds line segment to the collection and updates intersection vertices.
	 * Alters both segments and vertices
	 * @param   seg		line segment to add
	 * @param   segments	set of segments to add to
	 * @param   vertices	set of intersection vertices to update
	 */
	public static void addSegment(LineSegment seg, Collection<LineSegment> segments, List<Vertex> vertices) {
	    for (LineSegment l : segments) {
		if (seg.doIntersect(l)) {
		    addVertex(seg.intersection(l), vertices);
		}
	    }
	    segments.add(seg);
	}

	/**
	 * Adds vertex to collection of vertices, or merges visibility if
	 * a vertex with the same coordinates already exists.
	 * Alters vertices.
	 * @param   point	vertex to add
	 * @param   vertices	set of intersection vertices to update
	 */
	public static void addVertex(Vertex point, List<Vertex> vertices){
	    int index = vertices.indexOf(point);
	    if(index!=-1){
		vertices.get(index).mergeVertex(point);
	    }
	    else{
		vertices.add(point);
	    }
	}
	
	/**
	 * @return	LineSegment with completely random endpoint coordinates.
	 */
	public static LineSegment randomSegment() {
	    return new LineSegment("s0",
				    new BigFraction(rdm.nextInt(gridsize)),
				    new BigFraction(rdm.nextInt(gridsize)),
				    new BigFraction(rdm.nextInt(gridsize)),
				    new BigFraction(rdm.nextInt(gridsize)) 
				  );
	}

	//creates a random line segment guaranteed to intersect atleast one other
	public static LineSegment randomIntersectingSegment(ArrayList<LineSegment> segments, int linenum){
		//choose the first point
		LineSegment segment = segments.get(rdm.nextInt(segments.size()));
		Vertex pointA = null;
		do {
			pointA = randomPoint(gridsize);
		} while (onLine(segment, pointA));
		//choose the second point		
		Vertex pointB = null;
		ArrayList<Vertex> opposingpts = intersectingPts(pointA, segment);
		System.out.println("intersecting points found");
		Iterator<Vertex> itr = new RandomIterator<Vertex>(opposingpts, rdm);
		while (itr.hasNext()) {
		    pointB = itr.next();
		    //test if the segment created by  pointA and pointB is valid		
		    if (noOverlap(segments, pointA, pointB)) {
			return new LineSegment(""+linenum, pointA, pointB);
		    }
		}
		return randomIntersectingSegment(segments, linenum);
	}
	
	/**
	 * Tries to generate a line segment from one intersection to another
	 * without overlapping any existing segments. This is not always 
	 * possible so null is returned on failure.
	 * REQ: vertices contains at least 2 segments
	 * @param   vertices	collection of intersection points to choose from
	 * @param   segments	collection of existing segments 
	 * @param   linenum	the id to assign to the segment name
	 * @return  a LineSegment connecting a vertex to a vertex without 
	 *	    overlapping existing segments or null if none was found
	 */
	public static LineSegment
	vertexToVertex(List<Vertex> vertices,
		Collection<LineSegment> segments, int linenum)
	{
	    //Iterator<LineSegment> seg_itr = new RandomIterator<LineSegment>(segments, rdm);
	    Iterator<Vertex> P_itr = new RandomIterator<Vertex>(vertices, rdm);
	    Iterator<Vertex> Q_itr = new RandomIterator<Vertex>(vertices, rdm);
	    LineSegment seg = null;

	    Vertex P = null;
	    Vertex Q = null;
	    boolean success = false;
	    while (P_itr.hasNext()) {
		P = P_itr.next();
		while (Q_itr.hasNext()) {
		    Q = Q_itr.next();
		    if (noOverlap(segments, P, Q)) {
			success = true;
			break;
		    }
		}
		if (success) {
		    return new LineSegment(""+linenum, P.getX(), P.getY(), Q.getX(), Q.getY());
		}
	    } // else 
	    return null;
	}

	/**
	 * Generates a LineSegment with one endpoint on an intersection
	 * and the other at a random point, without overlapping any 
	 * existing segments.
	 * @param   segments	collection of existing segments
	 * @param   vertices	collection of intersection points to choose from
	 * @param   linenum	the id to assign to the segment name
	 * @return  a LineSegment with one endpoint being an intersection point 
	 *	    that does not overlap any existing segments
	 */
	public static LineSegment
	//vertexToRandom(List<? extends Vertex> vertices,
	//	List<? extends LineSegment> segments, int linenum)
	vertexToRandom(List<Vertex> vertices,
		List<LineSegment> segments, int linenum)
	{
	    Vertex pointA = vertices.get(rdm.nextInt(vertices.size()));
	    Vertex pointB = null;
	    do {
		pointB = randomPoint(gridsize);
	    } while(!noOverlap(segments, pointA, pointB));

	    return new LineSegment(""+linenum, pointA.getX(), pointA.getY(), pointB.getX(), pointB.getY());
	}

	//returns a random grid point
	public static Vertex randomPoint(int size){
		return new Vertex(new BigFraction(rdm.nextInt(size)), new BigFraction(rdm.nextInt(size)));
	}
	
	
	//given a vertex, and a line segment, it finds all intersecting points
	public static ArrayList<Vertex> intersectingPts(Vertex point, LineSegment segment){
		ArrayList<Vertex> validpts = new ArrayList<Vertex>();
		for(int x = 0; x < gridsize; x++){
			for(int y = 0; y < gridsize; y++){
				BigFraction xcoord = new BigFraction(x);
				BigFraction ycoord = new BigFraction(y);
				LineSegment testline = new LineSegment("test", xcoord, ycoord, point.getX(), point.getY());
				if(segment.doIntersect(testline)){
					validpts.add(new Vertex(xcoord, ycoord));					
				}
			}
		}
		return validpts;
	}
	
	
	//tests to see if the given vertex lies on the line corresponding
	//to the given line segment
	public static boolean onLine(LineSegment segment, Vertex point){
		BigFraction x = point.getX();
		BigFraction y = point.getY();
		
		//handle normal line
		if(segment.isNotVertical()){
			if(segment.yValue(x).equals(y)){
				return false;
			}
		}
		
		//handle vertical line
		else{
			if(segment.getX1()==x){
				return false;
			}
		}
		return true;
	}


	//finds y value for a line at a given x. Needed to avoid creating
	//new unnecessary line segments in method chooseSecondPt()
	public static BigFraction yValue(BigFraction x, BigFraction X1, BigFraction Y1, BigFraction X2, BigFraction Y2){
		if(X1!=X2){
			//(Y2-Y1)*x/(X2-X1)+Y1-(X1*(Y2-Y1)/(X2-X1));
			return (Y2.subtract(Y1)).multiply(x.divide(X2.subtract(X1))).add(Y1.subtract(X1.multiply(Y2.subtract(Y1)).divide(X2.subtract(X1)))); 
		}
		else{
			return new BigFraction(0);
		}
	}


	/**
	 * Tests if the two Vertices would form a line segment that overlaps 
	 * an existing one.
	 * @param   segments	collection of existing segments 
	 * @param   pointa	first endpoint of segment to test
	 * @param   pointb	second endpoint of segment to test
	 * @return  true if no overlap, false if overlap
	 */
	public static boolean noOverlap(Collection<LineSegment> segments, Vertex pointa, Vertex pointb){
		LineSegment l = new LineSegment(pointa, pointb);

		for(LineSegment m : segments){
			if (l.overlaps(m)) { return false; }
		}
		return true;
	}


	//min and max methods for BigFraction	
	public static BigFraction Max(BigFraction a, BigFraction b){
		if(a.compareTo(b)==1){
			return a;
		}
		else{
			return b;
		}
	}

	public static BigFraction Min(BigFraction a, BigFraction b){
		if(a.compareTo(b)==-1){
			return a;
		}
		else{
			return b;
		}
	}

}//end class
